include "num.pyx"
cdef uint PERTURB_SHIFT=5

cdef u64 next_u16_arrayset(u16* arrayset, u64* iptr):
    cdef u64 i=iptr[0]
    iptr[0]+=1
    return arrayset[i]

cdef u64 next_u16_hashset(u16* hashset, u64* iptr):
    cdef u64 i = iptr[0]
    while(hashset[i] == 0):
        i+=1
    return hashset[i]

cdef u64 bisect_u16_in(u16* arr, u64 val, uint count, uint* eq):
    cdef uint low=0, high=count, mi
    while(low<high):
        mi = (low+high)>>1
        if arr[mi]<val:
            low = mi + 1
        elif arr[mi]>val:
            high = mi
        else:
            eq[0]=1
            return mi
    eq[0]=0
    return low


cdef u64 bisect_insert_u16(u16* arr, u64 val, u64 count):
    cdef uint eq, i=bisect_u16_in(arr, val, count, &eq), ii, j
    cdef u16 temp0, temp1
    if eq:
        return UINT64_MAX
    else:
        temp0=val
        for ii in range(i,count):
            temp1 = arr[ii]
            arr[ii]=temp0
            temp0 = temp1
        arr[count]=temp0
        return i

cdef u64 bisect_remove_u16(u16* arr, u64 val, u64 count, ):
    cdef uint eq, i=bisect_u16_in(arr, val, count, &eq), ii, j
    cdef uInt temp0, temp1
    if eq:
        for ii in range(i,count-1):
            arr[ii]=arr[ii+1]
        return i
    else:
        return UINT64_MAX

cdef u64 u16_hash_search_in(u16* hashset, uint mask, u64 val):
    cdef u64 perturb = val
    cdef uint i=val&mask, j
    while(1):
        if hashset[i]==0:
            return UINT64_MAX
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return i
    raise AssertionError('Unreachable')


cdef u64 u16_hash_insert(u16* hashset, uint mask, u64 val):
    cdef u64 perturb = val
    cdef uint i=val&mask, j
    while(1):
        if hashset[i]==0:
            hashset[i]=val
            return i
        elif hashset[i]!=val:
            perturb >>= PERTURB_SHIFT
            i = mask & (i * 5 + perturb + 1)
        else:
            return UINT64_MAX

cdef u64 u16_remove_hash(u16* hashset, uint mask, u64 val):
    cdef u64 perturb = val
    cdef uint i=u16_hash_search_in(hashset, mask, val)
    if i!=UINT64_MAX:
        hashset[i]=0
    return i

